home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / archiver / lz13.zip / LZCOMP2.ASM < prev    next >
Assembly Source File  |  1988-10-20  |  8KB  |  303 lines
  1.     title    lzcomp - file compressor using limpel-ziv algorithm
  2.  
  3. ;Tom Pfau
  4. ;Digital Equipment Corporation
  5. ;Parsippany, NJ
  6. ;
  7. ;v1.2, Toad Hall Tweak
  8. ; - Converting to COM file.
  9. ; - Gonna use BP to hold bit_offset throughout (faster)
  10. ; - Moved most buffers outside code space.
  11.  
  12. ;Constants
  13. CLEAR        equ    256        ;Clear code
  14. EOF        equ    257        ;End of file marker
  15. FIRST_FREE    equ    258        ;First free code
  16. MAXMAX        equ    4096        ;Max code + 1
  17.  
  18.     include macros2.mlb
  19.  
  20. ;Hash table entry
  21. hash_rec    struc
  22. first    dw    ?            ; First entry with this value
  23. next    dw    ?            ; Next entry along chain
  24. char    db    ?            ; Suffix char
  25. hash_rec    ends
  26.  
  27. ;Declare Segments
  28. Code    segment para public 'code'
  29.     assume    CS:Code, DS:Code, ES:Code
  30.  
  31.     org    100H
  32.  
  33. LzComp    proc    near
  34.     jmp    Start
  35.  
  36. ;TH collecting all data segment stuff
  37. input_prompt    db    'Input file: $'
  38. output_prompt    db    'Output file: $'
  39. input_file    db    80,0,80 dup (?)
  40. output_file    db    80,0,80 dup (?)
  41. crlf        db    13,10,'$'
  42. input_handle    dw    0    ;?
  43. output_handle    dw    0    ;?
  44.  
  45. ;hash_seg    dw    hash SHR 4    ;convert to a segment?
  46. prefix_code    dw    0    ;?
  47. free_code    dw    0    ;?
  48. max_code    dw    0    ;?
  49. nbits        dw    0    ;?
  50. k        db    0    ;?
  51.  
  52. ;bit_offset    dw    0    ;?
  53. input_offset    dw    0
  54. input_size    dw    0
  55. LzComp    endp
  56.  
  57.  
  58. start    proc    near    ;far
  59. ;TH we won't mess with any memory allocating, since I think
  60. ;all required buffers, hash tables, etc. can work within
  61. ;a lousy 64Kb segment.
  62. ;Won't even bother moving the stackpointer for now either.
  63.  
  64.     print    input_prompt        ;Get input file name
  65.     input    input_file
  66.     print    crlf
  67.     print    output_prompt        ;And output
  68.     input    output_file
  69.     print    crlf
  70. ;Terminate file names with nulls
  71.     mov    al,input_file+1        ;input filename length
  72.     xor    ah,ah            ;clear msb
  73.     mov    si,ax            ;pointer is filename length
  74.     mov    input_file+2[si],0    ;point to last char+1, stuff 0
  75.     mov    al,output_file+1    ;output filename length
  76.     mov    si,ax            ;pointer is filename length
  77.     mov    output_file+2[si],0    ;point to last char+1, stuff 0
  78.     hopen    input_file+2,0
  79.     mov    input_handle,ax        ;save input file handle
  80.     hcreat    output_file+2,0
  81.     mov    output_handle,ax    ;save output file handle
  82.     call    compress        ;Compress file
  83.     hclose    input_handle        ;Close in and out
  84.     hclose    output_handle
  85.     exit                ;Done
  86. start    endp
  87.  
  88. compress    proc    near
  89.  
  90. l1:    call    init_table        ;Initialize the table and some vars
  91.     mov    ax,CLEAR        ;Write a clear code
  92.     call    write_code
  93.     call    read_char        ;Read first char
  94.  
  95. l4:    xor    ah,ah            ;Turn char into code
  96. l4a:    mov    prefix_code,ax        ;Set prefix code
  97.     call    read_char        ;Read next char
  98.     jc    l17            ;Carry means EOF
  99.     mov    k,al            ;Save char in k
  100.     mov    bx,prefix_code        ;Get prefix code
  101.     call    lookup_code        ;See if this pair in table
  102.     jnc    l4a            ;nc means yes, new code in ax
  103.     call    add_code        ;Add pair to table
  104.     push    bx            ;Save new code
  105.     mov    ax,prefix_code        ;Write old prefix code
  106.     call    write_code
  107.     pop    bx
  108.     mov    al,k            ;Get last char
  109.     cmp    bx,max_code        ;Exceed code size?
  110.     jl    l4            ;less means no
  111.     cmp    nbits,12        ;Currently less than 12 bits?
  112.     jl    l14            ;yes
  113.      mov    ax,CLEAR        ;Write a clear code
  114.      call    write_code
  115.      call    init_table        ;Reinit table
  116.      mov    al,k            ;get last char
  117.      jmp    l4            ;Start over
  118.  
  119. l14:    inc    nbits            ;Increase number of bits
  120.     shl    max_code,1        ;Double max code size
  121.     jmp    l4            ;Get next char
  122.  
  123. l17:    mov    ax,prefix_code        ;Write last code
  124.     call    write_code
  125.     mov    ax,EOF            ;Write EOF code
  126.     call    write_code
  127.     mov    ax,bp    ;bit_offset    ;Make sure buffer is flushed to file
  128.     or    ax,ax            ;TH
  129.     je    l18
  130.      mov    cx,8            ;convert bits to bytes
  131.      xor    dx,dx
  132.      div    cx
  133.      or    dx,dx            ;If extra bits, make sure they get
  134.      je    l17a            ;written
  135.       inc    ax
  136. l17a:     call    flush
  137. l18:    ret
  138. compress    endp
  139.  
  140. init_table    proc    near
  141.     mov    nbits,9            ;Set code size to 9
  142.     mov    max_code,512        ;Set max code to 512
  143.  
  144.     mov    ax,-1            ;Unused flag
  145.     mov    cx,640            ;Clear first 256 entries
  146.     mov    di,offset hash        ;TH Point to first entry
  147. rep    stosw                ;Clear it out
  148.     mov    free_code,FIRST_FREE    ;Set next code to use
  149.     ret                ;done
  150. init_table    endp
  151.  
  152. write_code    proc    near
  153.     push    ax            ;Save code
  154.     mov    ax,bp    ;bit_offset    ;Get bit offset
  155. ;TH we're keeping bit_offset in BP
  156. ;    mov    cx,nbits        ;Adjust bit offset by code size
  157. ;    add    bit_offset,cx
  158.     add    bp,nbits        ;TH adjust bit offset by code size
  159.     mov    cx,8            ;Convert bit offset to byte offset
  160.     xor    dx,dx
  161.     div    cx
  162.     cmp    ax,1020            ;Approaching end of buffer?
  163.     jl    wc1            ;less means no
  164.      call    flush            ;Write the buffer
  165. ;TH we're keeping bit_offset in BP
  166. ;     push    dx            ;dx contains offset within byte
  167. ;     add    dx,nbits        ;adjust by code size
  168. ;     mov    bit_offset,dx        ;new bit offset
  169. ;     pop    dx            ;restore dx
  170.      mov    bp,dx            ;TH dx contains offset within byte
  171.      add    bp,nbits        ;TH adjust by code size
  172.  
  173.      add    ax,offset output_data    ;Point to last byte
  174.      mov    si,ax            ;put in si
  175.      mov    al,[si]            ;move byte to first position
  176.      mov    byte ptr output_data,al
  177.      xor    ax,ax            ;Byte offset of zero
  178. wc1:    add    ax,offset output_data    ;Point into buffer
  179.     mov    di,ax            ;Destination
  180.     pop    ax            ;Restore code
  181.     mov    cx,dx            ;offset within byte
  182.     xor    dx,dx            ;dx will catch bits rotated out
  183.     jcxz    wc3            ;If offset in byte is zero, skip shift
  184. wc2:     shl    ax,1            ;Rotate code
  185.      rcl    dx,1
  186.      loop    wc2
  187.      or    al,[di]            ;Grab bits currently in buffer
  188. wc3:    stosw                ;Save data
  189.     mov    al,dl            ;Grab extra bits
  190.     stosb                ;and save
  191.     ret
  192. write_code    endp
  193.  
  194.  
  195. flush        proc    near
  196.     push    ax            ;Save all registers
  197. ;TH    push    bx            ;AX contains number of bytes to write
  198. ;TH    push    cx
  199.     push    dx
  200.     hwrite    output_handle,output_data,ax    ;write output file
  201.     pop    dx
  202. ;TH    pop    cx
  203. ;TH    pop    bx
  204.     pop    ax
  205.     ret
  206. flush        endp
  207.  
  208. read_char    proc    near
  209.     mov    di,input_offset        ;Anything left in buffer?
  210.     cmp    di,input_size
  211.     jl    rd1            ;less means yes
  212.     hread    input_handle,input_data,1024    ;Read next chunk of input
  213.     or    ax,ax            ;TH Anything left?
  214.     je    rd2            ;equal means no, finished
  215.  
  216.     mov    input_size,ax        ;Save bytes read
  217.     xor    di,di            ;TH clear DI
  218.     mov    input_offset,di    ;TH 0    ;Point to beginning of buffer
  219. rd1:
  220. ;TH the mov/add instrs below are faster than the LEA.
  221. ;    lea    si,input_data[di]    ;Point at character
  222.     mov    si,offset input_data    ;TH
  223.     add    si,di            ;Point at char
  224.     lodsb                ;Read it in
  225.     inc    input_offset        ;Adjust pointer
  226.     clc                ;Success
  227.     ret
  228.  
  229. rd2:    stc                ;Nothing left
  230.     ret
  231. read_char    endp
  232.  
  233.  
  234. lookup_code    proc    near
  235.     call    index            ;convert code to address
  236.     xor    di,di    ;TH         ;flag
  237.     cmp    [si].first,-1        ;Has this code been used?
  238.     je    gc4            ;equal means no
  239.  
  240.     inc    di            ;set flag
  241.     mov    bx,[si].first        ;Get first entry
  242. gc2:    call    index            ;convert code to address
  243.     cmp    [si].char,al        ;is char the same?
  244.     jne    gc3            ;ne means no
  245.      clc                ;success
  246.      mov    ax,bx            ;put found code in ax
  247.      ret                ;done
  248.  
  249. gc3:    cmp    [si].next,-1        ;More left with this prefix?
  250.     je    gc4            ;equal means no
  251.      mov    bx,[si].next        ;get next code
  252.      jmp    gc2            ;try again
  253.  
  254. gc4:    stc                ;not found
  255.     ret                ;done
  256. lookup_code    endp
  257.  
  258.  
  259. index        proc    near
  260.     mov    si,bx            ;si = bx * 5 (5 byte hash entries)
  261.     shl    si,1            ;si = bx * 2 * 2 + bx
  262.     shl    si,1
  263.     add    si,bx
  264.     add    si,offset hash        ;TH plus hash table base
  265.     ret
  266. index        endp
  267.  
  268. add_code    proc    near
  269. ;Only called once
  270.     mov    bx,free_code        ;Get code to use
  271.     or    di,di    ;TH        ;First use of this prefix?
  272.     je    ac1            ;equal means yes
  273.      mov    [si].next,bx        ;point last use to new entry
  274.      jmp    short ac2
  275.  
  276. ac1:    mov    [si].first,bx        ;Point first use to new entry
  277. ac2:    cmp    bx,MAXMAX        ;Have we reached code limit?
  278.     je    ac3            ;equal means yes, just return
  279.      call    index            ;get address of new entry
  280. ;TH switched around a little
  281.      mov    [si].char,al        ;save suffix char
  282.      mov    ax,-1            ;TH do this once (ok to destroy AX)
  283.      mov    [si].first,ax    ;-1    ;initialize pointers
  284.      mov    [si].next,ax    ;-1
  285.      inc    free_code        ;TH adjust next code
  286. ac3:    ret
  287. add_code    endp
  288.  
  289. ;TH input/output buffers moved here outside code space
  290.     even
  291.  
  292. output_data    equ    $            ;db    1024 dup (?)
  293. input_data    equ    output_data+1024    ;db    1024 dup (?)
  294.  
  295. ;Instead of using a separate segment for memory and the hash
  296. ;table (with all the resultant segment register fiddling),
  297. ;gonna just use a dynamic buffer right in code space.
  298.  
  299. hash    equ    input_data+1024
  300.  
  301. code    ends
  302.     end    LzComp
  303.